package com.xiaoyu.arrays;

import java.util.HashMap;

/**
 * @program: DS_and_A
 * @description: 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 *
 * 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题
 * @author: YuWenYi
 * @create: 2021-05-09 15:16
 **/
public class MajorityElement {
    //方法一:使用map记录法,优点是简单易懂缺点是占用空间较大并且速度较慢
    public static int majorityElement1(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
            if (map.get(num) > nums.length/2){
                return num;
            }
        }
        //如果存在多数元素,那么是不会走到这行的
        return Integer.MIN_VALUE;
    }

    //Boyer-Moore 投票算法,遍历数组,选出count数量大于0的候选者
    public static int majorityElement(int[] nums) {
        int count = 0;   //众数出现的次数,即得票数
        int candidate = 0;  //众数候选者

        for (int num : nums) {
            if (count == 0) {  //如果count等于0,就换候选人
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;  //如果num不是候选的众数,那么就抵消一次票数
        }

        return candidate;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{2,2,1,1,1,2,2};
        int element = majorityElement(nums);
        System.out.println(element);
    }
}
